﻿using System;

namespace ProblemsSet
{
    public class Problem_150 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 1000;
            //const int max = 6;

            var test = new []
                           {
                               new long[]{15},
                               new long[]{-14,-7},
                               new long[]{20,-13,-5},
                               new long[]{-3, 8, 23 ,-26},
                               new long[]{1, -4, -5, -18, 5},
                               new long[]{-16, 31, 2, 9, 28, 3}
                           };

            var real = new long[max][];
            var left = new long[max][];
            var right = new long[max][];
            var down = new long[max][];
            long t = 0;
            var mod = (long) (Math.Pow(2, 20));

            long min = 0;

            for (var i = 1; i <= max; i++)
            {
                real[i - 1] = new long[i];
                right[i - 1] = new long[i];
                left[i - 1] = new long[i];
                down[i - 1] = new long[i];
                for (int j = 1; j <= i; j++)
                {
                    t = (615949*t + 797807)%mod;
                    var tmp = t - mod / 2;
                    real[i - 1][j - 1] = tmp;
                    if (min > tmp)
                        min = tmp;
                }
            }

            //real = test;
            //min = -26;

            for (var i = 0; i < max; i++)
            {
                for (var j = 0; j <= i; j++)
                {
                    if (i == j)
                        left[i][j] = real[i][j];
                    else
                        left[i][j] = left[i - 1][j] + real[i][j];

                    if (j == 0)
                    {
                        right[i][j] = real[i][j];
                        down[i][j] = real[i][j];
                    }
                    else
                    {
                        right[i][j] = right[i - 1][j - 1] + real[i][j];
                        down[i][j] = down[i][j - 1] + real[i][j];
                    }
                }
            }

            long full = real[max - 1][0];

            for (long width = 1; width < max; width++)
            {
                full += right[max - 1][width];
                if (min > full)
                    min = full;
                long withoutLeft = full;
                for (long offLeft = -1; offLeft < width-1; offLeft++)
                {
                    if (offLeft >= 0)
                    {
                        withoutLeft -= left[max - 1][offLeft];
                        if (width < max - 1)
                            withoutLeft += left[max + offLeft - width - 2][offLeft];
                    }
                    if (withoutLeft < min)
                        min = withoutLeft;
                    long withoutHeight = withoutLeft;
                    for (long height = max-1; height>=max+offLeft-width+2; height--)
                    {
                        withoutHeight -= down[height][height-max+width+1];
                        if (offLeft >= 0)
                            withoutHeight += down[height][offLeft];
                        if (withoutHeight < min)
                            min = withoutHeight;
                    }
                }

            }

            return min;
        }

        private static BigInteger GetTriangleMaxSum(ref long[][] arr, int x, int y, int height)
        {
            BigInteger cur = 0;
            BigInteger res = 0;
            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j <= i; j++)
                {
                    cur += arr[y + i][x + j];
                }
                if (i == 0 || res > cur)
                    res = cur;
            }
            return res;
        }

        public override string Problem
        {
            get
            {
                return @"In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of 42.


We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers sk in the range 219, using a type of random number generator (known as a Linear Congruential Generator) as follows:

t := 0 
for k = 1 up to k = 500500: 
    t := (615949*t + 797807) modulo 220 
    sk := t219
Thus: s1 = 273519, s2 = 153582, s3 = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s1 
s2  s3 
s4  s5  s6  
s7  s8  s9  s10 
...
Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on). 
The 'sum of a sub-triangle' is defined as the sum of all the elements it contains. 
Find the smallest possible sub-triangle sum.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return -271248680;
            }
        }
    }
}
